<!-- HTML header for doxygen 1.8.6-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<title>OpenCV: Optical Flow</title>
<link href="../../opencv.ico" rel="shortcut icon" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="../../tutorial-utils.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          matTT: [ "\\[ \\left|\\begin{array}{ccc} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{array}\\right| \\]", 9],
          fork: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ \\end{array} \\right.", 4],
          forkthree: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ \\end{array} \\right.", 6],
          forkfour: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ #7 & \\mbox{#8}\\\\ \\end{array} \\right.", 8],
          vecthree: ["\\begin{bmatrix} #1\\\\ #2\\\\ #3 \\end{bmatrix}", 3],
          vecthreethree: ["\\begin{bmatrix} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{bmatrix}", 9],
          cameramatrix: ["#1 = \\begin{bmatrix} f_x & 0 & c_x\\\\ 0 & f_y & c_y\\\\ 0 & 0 & 1 \\end{bmatrix}", 1],
          distcoeffs: ["(k_1, k_2, p_1, p_2[, k_3[, k_4, k_5, k_6 [, s_1, s_2, s_3, s_4[, \\tau_x, \\tau_y]]]]) \\text{ of 4, 5, 8, 12 or 14 elements}"],
          distcoeffsfisheye: ["(k_1, k_2, k_3, k_4)"],
          hdotsfor: ["\\dots", 1],
          mathbbm: ["\\mathbb{#1}", 1],
          bordermatrix: ["\\matrix{#1}", 1]
      }
  }
}
);
//]]>
</script><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../stylesheet.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<!--#include virtual="/google-search.html"-->
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="../../opencv-logo-small.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenCV
   &#160;<span id="projectnumber">4.5.2</span>
   </div>
   <div id="projectbrief">Open Source Computer Vision</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search",false,'Search');
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('../../',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="../../d5/d10/tutorial_js_root.html">OpenCV.js Tutorials</a></li><li class="navelem"><a class="el" href="../../de/db6/tutorial_js_table_of_contents_video.html">Video Analysis</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">Optical Flow </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Goal </h2>
<ul>
<li>We will understand the concepts of optical flow and its estimation using Lucas-Kanade method.</li>
<li>We will use functions like <b><a class="el" href="../../dc/d6b/group__video__track.html#ga473e4b886d0bcc6b65831eb88ed93323" title="Calculates an optical flow for a sparse feature set using the iterative Lucas-Kanade method with pyra...">cv.calcOpticalFlowPyrLK()</a></b> to track feature points in a video.</li>
</ul>
<h2>Optical Flow </h2>
<p>Optical flow is the pattern of apparent motion of image objects between two consecutive frames caused by the movement of object or camera. It is 2D vector field where each vector is a displacement vector showing the movement of points from first frame to second. Consider the image below (Image Courtesy: <a href="http://en.wikipedia.org/wiki/Optical_flow">Wikipedia article on Optical Flow</a>).</p>
<div class="image">
<img src="../../optical_flow_basic1.jpg" alt="optical_flow_basic1.jpg"/>
<div class="caption">
image</div></div>
<p> It shows a ball moving in 5 consecutive frames. The arrow shows its displacement vector. Optical flow has many applications in areas like :</p>
<ul>
<li>Structure from Motion</li>
<li>Video Compression</li>
<li>Video Stabilization ...</li>
</ul>
<p>Optical flow works on several assumptions:</p>
<ol type="1">
<li>The pixel intensities of an object do not change between consecutive frames.</li>
<li>Neighbouring pixels have similar motion.</li>
</ol>
<p>Consider a pixel \(I(x,y,t)\) in first frame (Check a new dimension, time, is added here. Earlier we were working with images only, so no need of time). It moves by distance \((dx,dy)\) in next frame taken after \(dt\) time. So since those pixels are the same and intensity does not change, we can say,</p>
<p class="formulaDsp">
\[I(x,y,t) = I(x+dx, y+dy, t+dt)\]
</p>
<p>Then take taylor series approximation of right-hand side, remove common terms and divide by \(dt\) to get the following equation:</p>
<p class="formulaDsp">
\[f_x u + f_y v + f_t = 0 \;\]
</p>
<p>where:</p>
<p class="formulaDsp">
\[f_x = \frac{\partial f}{\partial x} \; ; \; f_y = \frac{\partial f}{\partial y}\]
</p>
 <p class="formulaDsp">
\[u = \frac{dx}{dt} \; ; \; v = \frac{dy}{dt}\]
</p>
<p>Above equation is called Optical Flow equation. In it, we can find \(f_x\) and \(f_y\), they are image gradients. Similarly \(f_t\) is the gradient along time. But \((u,v)\) is unknown. We cannot solve this one equation with two unknown variables. So several methods are provided to solve this problem and one of them is Lucas-Kanade.</p>
<h3>Lucas-Kanade method</h3>
<p>We have seen an assumption before, that all the neighbouring pixels will have similar motion. Lucas-Kanade method takes a 3x3 patch around the point. So all the 9 points have the same motion. We can find \((f_x, f_y, f_t)\) for these 9 points. So now our problem becomes solving 9 equations with two unknown variables which is over-determined. A better solution is obtained with least square fit method. Below is the final solution which is two equation-two unknown problem and solve to get the solution.</p>
<p class="formulaDsp">
\[\begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} \sum_{i}{f_{x_i}}^2 &amp; \sum_{i}{f_{x_i} f_{y_i} } \\ \sum_{i}{f_{x_i} f_{y_i}} &amp; \sum_{i}{f_{y_i}}^2 \end{bmatrix}^{-1} \begin{bmatrix} - \sum_{i}{f_{x_i} f_{t_i}} \\ - \sum_{i}{f_{y_i} f_{t_i}} \end{bmatrix}\]
</p>
<p>( Check similarity of inverse matrix with Harris corner detector. It denotes that corners are better points to be tracked.)</p>
<p>So from user point of view, idea is simple, we give some points to track, we receive the optical flow vectors of those points. But again there are some problems. Until now, we were dealing with small motions. So it fails when there is large motion. So again we go for pyramids. When we go up in the pyramid, small motions are removed and large motions becomes small motions. So applying Lucas-Kanade there, we get optical flow along with the scale.</p>
<h2>Lucas-Kanade Optical Flow in OpenCV.js </h2>
<p>We use the function: <b><a class="el" href="../../dc/d6b/group__video__track.html#ga473e4b886d0bcc6b65831eb88ed93323" title="Calculates an optical flow for a sparse feature set using the iterative Lucas-Kanade method with pyra...">cv.calcOpticalFlowPyrLK</a> (prevImg, nextImg, prevPts, nextPts, status, err, winSize = new cv.Size(21, 21), maxLevel = 3, criteria = new <a class="el" href="../../d9/d5d/classcv_1_1TermCriteria.html" title="The class defining termination criteria for iterative algorithms. ">cv.TermCriteria</a>(cv.TermCriteria_COUNT+ cv.TermCriteria_EPS, 30, 0.01), flags = 0, minEigThreshold = 1e-4)</b>. </p><dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">prevImg</td><td>first 8-bit input image or pyramid constructed by buildOpticalFlowPyramid. </td></tr>
    <tr><td class="paramname">nextImg</td><td>second input image or pyramid of the same size and the same type as prevImg. </td></tr>
    <tr><td class="paramname">prevPts</td><td>vector of 2D points for which the flow needs to be found; point coordinates must be single-precision floating-point numbers. </td></tr>
    <tr><td class="paramname">nextPts</td><td>output vector of 2D points (with single-precision floating-point coordinates) containing the calculated new positions of input features in the second image; when cv.OPTFLOW_USE_ INITIAL_FLOW flag is passed, the vector must have the same size as in the input. </td></tr>
    <tr><td class="paramname">status</td><td>output status vector (of unsigned chars); each element of the vector is set to 1 if the flow for the corresponding features has been found, otherwise, it is set to 0. </td></tr>
    <tr><td class="paramname">err</td><td>output vector of errors; each element of the vector is set to an error for the corresponding feature, type of the error measure can be set in flags parameter; if the flow wasn't found then the error is not defined (use the status parameter to find such cases). </td></tr>
    <tr><td class="paramname">winSize</td><td>size of the search window at each pyramid level. </td></tr>
    <tr><td class="paramname">maxLevel</td><td>0-based maximal pyramid level number; if set to 0, pyramids are not used (single level), if set to 1, two levels are used, and so on; if pyramids are passed to input then algorithm will use as many levels as pyramids have but no more than maxLevel. </td></tr>
    <tr><td class="paramname">criteria</td><td>parameter, specifying the termination criteria of the iterative search algorithm (after the specified maximum number of iterations criteria.maxCount or when the search window moves by less than criteria.epsilon. </td></tr>
    <tr><td class="paramname">flags</td><td>operation flags:<ul>
<li><a class="el" href="../../dc/d6b/group__video__track.html#gga1d74616b51e7bc4f312a6978690c98b4a9d4430ac75199af0cf6fcdefba30eafe">cv.OPTFLOW_USE_INITIAL_FLOW</a> uses initial estimations, stored in nextPts; if the flag is not set, then prevPts is copied to nextPts and is considered the initial estimate.</li>
<li><a class="el" href="../../dc/d6b/group__video__track.html#gga1d74616b51e7bc4f312a6978690c98b4add75f0bd85d1bd739b39b8900bc12c58">cv.OPTFLOW_LK_GET_MIN_EIGENVALS</a> use minimum eigen values as an error measure (see minEigThreshold description); if the flag is not set, then L1 distance between patches around the original and a moved point, divided by number of pixels in a window, is used as a error measure. </li>
</ul>
</td></tr>
    <tr><td class="paramname">minEigThreshold</td><td>the algorithm calculates the minimum eigen value of a 2x2 normal matrix of optical flow equations, divided by number of pixels in a window; if this value is less than minEigThreshold, then a corresponding feature is filtered out and its flow is not processed, so it allows to remove bad points and get a performance boost.</td></tr>
  </table>
  </dd>
</dl>
<h3>Try it</h3>
<p> 
<iframe src="../../js_optical_flow_lucas_kanade.html" width="100%"
        onload="this.style.height=this.contentDocument.body.scrollHeight +'px';">
</iframe>
</p>
<p>(This code doesn't check how correct are the next keypoints. So even if any feature point disappears in image, there is a chance that optical flow finds the next point which may look close to it. So actually for a robust tracking, corner points should be detected in particular intervals.)</p>
<h2>Dense Optical Flow in OpenCV.js </h2>
<p>Lucas-Kanade method computes optical flow for a sparse feature set (in our example, corners detected using Shi-Tomasi algorithm). OpenCV.js provides another algorithm to find the dense optical flow. It computes the optical flow for all the points in the frame. It is based on Gunner Farneback's algorithm which is explained in "Two-Frame Motion Estimation Based on Polynomial Expansion" by Gunner Farneback in 2003.</p>
<p>We use the function: <b><a class="el" href="../../dc/d6b/group__video__track.html#ga5d10ebbd59fe09c5f650289ec0ece5af" title="Computes a dense optical flow using the Gunnar Farneback&#39;s algorithm. ">cv.calcOpticalFlowFarneback</a> (prev, next, flow, pyrScale, levels, winsize, iterations, polyN, polySigma, flags)</b> </p><dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">prev</td><td>first 8-bit single-channel input image. </td></tr>
    <tr><td class="paramname">next</td><td>second input image of the same size and the same type as prev. </td></tr>
    <tr><td class="paramname">flow</td><td>computed flow image that has the same size as prev and type CV_32FC2. </td></tr>
    <tr><td class="paramname">pyrScale</td><td>parameter, specifying the image scale (&lt;1) to build pyramids for each image; pyrScale=0.5 means a classical pyramid, where each next layer is twice smaller than the previous one. </td></tr>
    <tr><td class="paramname">levels</td><td>number of pyramid layers including the initial image; levels=1 means that no extra layers are created and only the original images are used. </td></tr>
    <tr><td class="paramname">winsize</td><td>averaging window size; larger values increase the algorithm robustness to image noise and give more chances for fast motion detection, but yield more blurred motion field. </td></tr>
    <tr><td class="paramname">iterations</td><td>number of iterations the algorithm does at each pyramid level. </td></tr>
    <tr><td class="paramname">polyN</td><td>size of the pixel neighborhood used to find polynomial expansion in each pixel; larger values mean that the image will be approximated with smoother surfaces, yielding more robust algorithm and more blurred motion field, typically polyN =5 or 7. </td></tr>
    <tr><td class="paramname">polySigma</td><td>standard deviation of the Gaussian that is used to smooth derivatives used as a basis for the polynomial expansion; for polyN=5, you can set polySigma=1.1, for polyN=7, a good value would be polySigma=1.5. </td></tr>
    <tr><td class="paramname">flags</td><td>operation flags that can be a combination of the following:<ul>
<li><a class="el" href="../../dc/d6b/group__video__track.html#gga1d74616b51e7bc4f312a6978690c98b4a9d4430ac75199af0cf6fcdefba30eafe">cv.OPTFLOW_USE_INITIAL_FLOW</a> uses the input flow as an initial flow approximation.</li>
<li><a class="el" href="../../dc/d6b/group__video__track.html#gga1d74616b51e7bc4f312a6978690c98b4a4ffe37adbc548e44a61025a26a1914aa">cv.OPTFLOW_FARNEBACK_GAUSSIAN</a> uses the Gaussian 𝚠𝚒𝚗𝚜𝚒𝚣𝚎×𝚠𝚒𝚗𝚜𝚒𝚣𝚎 filter instead of a box filter of the same size for optical flow estimation; usually, this option gives z more accurate flow than with a box filter, at the cost of lower speed; normally, winsize for a Gaussian window should be set to a larger value to achieve the same level of robustness.</li>
</ul>
</td></tr>
  </table>
  </dd>
</dl>
<h3>Try it</h3>
<p> 
<iframe src="../../js_optical_flow_dense.html" width="100%"
        onload="this.style.height=this.contentDocument.body.scrollHeight +'px';">
</iframe>
 </p>
</div></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.6-->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Apr 2 2021 11:36:37 for OpenCV by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="../../doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
<script type="text/javascript">
//<![CDATA[
addTutorialsButtons();
//]]>
</script>
</body>
</html>
